package com.cjm.algorithm.leetcode;

import java.util.*;

public class SortColor75 {

    /**
     * 这种思路,并没有三路快排快
     * @param nums
     */
    public static void sortColors1(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int k = i;
            while (k > 0 && nums[k] < nums[k-1]) {
                swap(nums, k, k - 1);
                k--;
            }
        }
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 这就是一个近乎有序的数组进行排序的问题
     *
     * @param nums
     */
    public static void sortColors(int[] nums) {
        Map<Integer, List<Integer>> mapInteger = new HashMap<>();
        mapInteger.put(0, new ArrayList<>());
        mapInteger.put(1, new ArrayList<>());
        mapInteger.put(2, new ArrayList<>());

        for (int i = 0; i < nums.length; i++) {
            mapInteger.get(nums[i]).add(nums[i]);
        }
        List<Integer> l0 = mapInteger.get(0);
        List<Integer> l1 = mapInteger.get(1);
        List<Integer> l2 = mapInteger.get(2);

        int k = 0;

        int i = 0;
        int j = 0;
        int x = 0;
        while (k < nums.length) {
            if (i < l0.size()) {
                nums[k] = l0.get(i);
                i++;
                k++;
                continue;
            }
            if (j < l1.size()) {
                nums[k] = l1.get(j);
                j++;
                k++;
                continue;
            }
            if (x < l2.size()) {
                nums[k] = l2.get(x);
                x++;
                k++;
                continue;
            }
        }
    }

    public static void main(String[] args) {
        int[] temp = new int[]{2, 0, 2, 1, 1, 0};
//        int[] temp = new int[]{2, 0, 1};
        sortColors1(temp);
        System.err.println("OK");
    }

}
